package problem;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

public class S_128 {
    //最长连续序列
    /*给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。*/
    //1.暴力,遍历每个数字找到其最长序列,超时
    class Solution {
        public boolean contains(int[] nums,int num){
            for(int i:nums){
                if(i==num) return true;
            }
            return false;
        }
        public int longestConsecutive(int[] nums) {
            int longMax=0;
            for(int num:nums){
                int current=num;
                int len=1;
                while(contains(nums,current+1)){
                    current+=1;
                    len+=1;
                }
                longMax=Math.max(len,longMax);
            }
            return longMax;
        }
    }

    //2.先排好序
    class Solution1 {
        public int longestConsecutive(int[] nums) {
            if (nums.length == 0) {
                return 0;
            }

            Arrays.sort(nums);

            int longestStreak = 1;
            int currentStreak = 1;

            for (int i = 1; i < nums.length; i++) {
                if (nums[i] != nums[i-1]) {
                    if (nums[i] == nums[i-1]+1) {
                        currentStreak += 1;
                    }
                    else {
                        longestStreak = Math.max(longestStreak, currentStreak);
                        currentStreak = 1;
                    }
                }
            }

            return Math.max(longestStreak, currentStreak);
        }
    }
    //3.哈希表
    class Solution3{
        public int longestConsecutive(int[] nums) {
            Set<Integer> num_set = new HashSet<Integer>();
            for (int num : nums) {
                num_set.add(num);
            }

            int longestStreak = 0;

            for (int num : num_set) {
                if (!num_set.contains(num-1)) {
                    int currentNum = num;
                    int currentStreak = 1;

                    while (num_set.contains(currentNum+1)) {
                        currentNum += 1;
                        currentStreak += 1;
                    }

                    longestStreak = Math.max(longestStreak, currentStreak);
                }
            }

            return longestStreak;
        }
    }

}
